package 中等.树;

import java.util.Arrays;

/**
 * 给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个
 * 硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为
 *  x ，那么称，你可以 构造 出 x 。
 * 请返回从 0 开始（包括 0 ），你最多能 构造 出多少个连续整数。
 * 你可能有多个相同值的硬币。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-number-of-consecutive-values-you-can-make
 */
public class 你能构造出连续值的最大数目_1798 {

    public static void main(String[] args) {

        System.out.println(getMaximumConsecutive(new int[]{1, 3}));

    }

    /**
     * 排序+贪心
     * 排序对结果不造成影响，先排序
     * 1，假设已经能构造出的区间为 [0,x]，然后再新增一个数 y
     * 范围变成 [y,x+y]，例如：[0,3] 当 y > (x+1=4) 时，假设
     * y = 5，那么这个区间变成 [0,3] [4,8] 没有 5 这个区间是
     * 不连贯的，只有当 y <= x+1 时，区间变成 [0,x+y]
     */
    public static int getMaximumConsecutive(int[] coins) {
        int x = 0;

        Arrays.sort(coins);
        for (int coin : coins) {
            // 硬币已经从小到大排序好，如果当前硬币不满足条件
            // 其右边更大的硬币，更加不能满足条件
            if (coin > x + 1) {
                break;
            }
            x += coin;
        }

        return x + 1;
    }

}
